#define _CRT_SECURE_NO_WARNINGS 1
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* sortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
    {
        return head;
    }

    struct ListNode* slow = head;
    struct ListNode* fast = head->next;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    struct ListNode* tmp = slow->next;
    slow->next = NULL;
    struct ListNode* left = sortList(head);
    struct ListNode* right = sortList(tmp);

    struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newhead->next = NULL;
    struct ListNode* res = newhead;

    while (left && right)
    {
        if (left->val < right->val)
        {
            res->next = left;
            left = left->next;
        }
        else
        {
            res->next = right;
            right = right->next;
        }
        res = res->next;
    }
    if (left)
    {
        res->next = left;
    }
    if (right)
    {
        res->next = right;
    }

    return newhead->next;
}